import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class YuSeFU {
    class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }

    }


    public int getResult1(int n,int m) {  //约瑟夫问题一
        if (n < 1) {
            return -1;
        }
        Node first = null;
        Node last = null;
        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                first = new Node(i);
                first.next = first;
                last = first;
                continue;
            }
            Node node = new Node(i);
            last.next = node;
            node.next = first;
            last = node;
        }
        while (last != first) {
            for (int i = 0; i < m-1; i++) {
                first = first.next;
                last = last.next;
            }
            last.next = first.next;
            first = first.next;
        }
        return first.val;
    }

    public int getResult(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        int m = 2;
        while (list.size() > m) {
            ArrayList<Integer> tmp = new ArrayList<>();
            tmp.add(0);
            for (int i = 0; i < list.size(); i = i+m) {
                tmp.add(list.get(i));
            }
            tmp.set(0,tmp.remove(tmp.size()-1));
            list = tmp;
            m++;
        }
        return list.get(0);
    }
}
